package org.hot100_0.leetcode31;

import java.util.Arrays;

public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        int [] test = {5,1,1};
        solution.nextPermutation(test);

        for (int num:test) {
            System.out.println(num);
        }
    }
    public void nextPermutation(int[] nums) {

        int n = nums.length;
        int end = n-1;
        if (n==1){
            return;
        }
        //从后往前
        int piv = n-2;

        while (piv>=0){
            if (nums[piv]<nums[piv+1]){
                int swapIndex = piv+1;
                while (swapIndex<=end && nums[swapIndex]>nums[piv]){
                    swapIndex++;
                }
                swap(nums,piv,swapIndex-1);
                Arrays.sort(nums,piv+1,end+1);
//                reverse(nums,swapIndex-1,end);
                return;
            }
            piv--;
        }

        reverse(nums,0,end);

    }

    private void swap(int [] arr,int index1,int index2){
            int temp = arr[index1];
            arr[index1] = arr[index2];
            arr[index2] = temp;
    }

    private void reverse(int [] arr,int start,int end){
        if (start>=end){
            return;
        }

        while (start<end){
            swap(arr,start,end);
            start++;
            end--;
        }
    }

}
